﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace _04.DicHashSet
{
    /// <summary>
    /// Implementation of <see cref="IDictionary"/> interface
    /// using hash table. Collisions are resolved by chaining.
    /// </summary>
    /// <typeparam name="K">Type of the keys</typeparam>
    /// <typeparam name="V">Type of the values</typeparam>
    public class HashDictionary<K, V> : IEnumerable<KeyValuePair<K, V>>
    {
        private const int DEFAULT_CAPACITY = 2;
        private const float DEFAULT_LOAD_FACTOR = 0.75f;
        private List<KeyValuePair<K, V>>[] table;
        private float loadFactor;
        private int threshold;
        private int size;
        private int initialCapacity;
        private int currentLoad;

        public HashDictionary()
            : this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR)
        {
        }

        private HashDictionary(int capacity, float loadFactor)
        {
            this.initialCapacity = capacity;
            this.table = new List<KeyValuePair<K, V>>[capacity];
            this.loadFactor = loadFactor;
            this.currentLoad = 0;
            unchecked
            {
                this.threshold = (int)(capacity * this.loadFactor);
            }
        }

        #region Properties

        public int Count
        {
            get
            {
                return this.size;
            }
        }

        public V this[K key]
        {
            get
            {
                return this.Get(key);
            }
            set
            {
                this.Set(key, value);
            }
        }

        public ICollection<K> Keys
        {
            get
            {
                List<K> returnKeys = new List<K>();
                foreach (List<KeyValuePair<K, V>> item in table)
                {
                    if (item != null)
                    {
                        foreach (KeyValuePair<K, V> element in item)
                        {
                            returnKeys.Add(element.Key);
                        }
                    }
                }
                return returnKeys;
            }
        }

        public ICollection<V> Values 
        {
            get 
            {
                List<V> returnValues = new List<V>();
                foreach (List<KeyValuePair<K, V>> item in table)
                {
                    if (item != null)
                    {
                        foreach (KeyValuePair<K, V> element in item)
                        {
                            returnValues.Add(element.Value);
                        }
                    }
                }
                return returnValues;
            }
        }

        #endregion

        #region Methods

        public void Set(K key, V value)
        {
            if (currentLoad >= threshold)
            {
                Expand();
            }

            List<KeyValuePair<K, V>> chain = this.FindChain(key, true);

            foreach (var item in chain)
            {
                if (item.Key.Equals(key))
                {
                    throw new ArgumentException("An element with the same key already exists in the HashDictionary<TKey, TValue>.");
                }
            }
            chain.Add(new KeyValuePair<K, V>(key, value));
            size++;
        }

        public V Get(K key)
        {
            List<KeyValuePair<K, V>> chain = this.FindChain(key, false);
            if (chain != null)
            {
                foreach (KeyValuePair<K, V> entry in chain)
                {
                    if (entry.Key.Equals(key))
                    {
                        return entry.Value;
                    }
                }
            }
            throw new Exception("Key not exist.");
        }

        public void Clear()
        {
            if (this.table != null)
            {
                this.table = new List<KeyValuePair<K, V>>[initialCapacity];
            }
            this.size = 0;
            this.currentLoad = 0;
        }

        public bool Remove(K key)
        {
            List<KeyValuePair<K, V>> chain = this.FindChain(key, false);

            if (chain != null)
            {
                for (int i = 0; i < chain.Count; i++)
                {
                    KeyValuePair<K, V> entry = chain[i];
                    if (entry.Key.Equals(key))
                    {
                        chain.RemoveAt(i);
                        this.size--;   
                        return true;
                    }
                }
            }
            return false;
        }

        private void Expand()
        {
            int newCapacity = 2 * this.table.Length;
            List<KeyValuePair<K, V>>[] oldTable = this.table;
            this.table = new List<KeyValuePair<K, V>>[newCapacity];
            this.threshold = (int)(newCapacity * this.loadFactor);
            this.currentLoad = 0;
            foreach (List<KeyValuePair<K, V>> oldChain in oldTable)
            {
                if (oldChain != null)
                {
                    foreach (KeyValuePair<K, V> keyValuePair in oldChain)
                    {
                        List<KeyValuePair<K, V>> chain = FindChain(keyValuePair.Key, true);
                        chain.Add(keyValuePair);
                    }
                }
            }
        }

        private List<KeyValuePair<K, V>> FindChain(K key, bool createIfMissing)
        {
            int index = key.GetHashCode();
            index = Math.Abs(index % this.table.Length);

            if (this.table[index] == null && createIfMissing)
            {
                this.table[index] = new List<KeyValuePair<K, V>>();
                this.currentLoad++;
            }
            return this.table[index] as List<KeyValuePair<K, V>>;
        }

        #endregion

        #region IEnumerable

        IEnumerator<KeyValuePair<K, V>> IEnumerable<KeyValuePair<K, V>>.GetEnumerator()
        {
            foreach (List<KeyValuePair<K, V>> chain in this.table)
            {
                if (chain != null)
                {
                    foreach (KeyValuePair<K, V> entry in chain)
                    {
                        yield return entry;
                    }
                }
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<KeyValuePair<K, V>>)this).
            GetEnumerator();
        }

        #endregion
    }
}
